1. Field of the Invention
The present invention relates generally to an ad-hoc sensor network including a plurality of nodes. More particularly, the present invention relates to a method for flooding a packet from a source node to a destination node.
2. Description of the Related Art
A general mobile communication system delivers data between a mobile element and a base station. The mobile element transceives data directly with the base station without passing through other mobile elements or nodes. Meanwhile, an ad-hoc sensor network transmits a packet from a source node to a destination node via other nodes. The following is an explanation of how a node in the ad-hoc sensor network floods a packet to establish a routing path.
FIG. 1 depicts a structure of a general ad-hoc network. The ad-hoc network is constructed of a plurality of nodes including a source node and a destination node. The source node requests the setting of a route to transmit data to the destination node. Typically, the nodes in the ad-hoc network are mobile. Hence, packet flooding is required to set the route in the ad-hoc network. Hereinafter, it will be described how to flood the packet to the destination node by the source node.
The source node, which requests to set the route, generates a route request packet. The route request packet contains an address of the source node and that of the destination node. Other nodes in the ad-hoc network determine if they are the destination node based on the destination address contained in the received packet.
The source node broadcasts the generated packet. The broadcast packet from the source node reaches one-hop nodes. In FIG. 1, the one-hop nodes from the source node are nodes 1 through 5. The nodes 1 to 5 compare the destination address contained in the received packet with their addresses. If the destination address and their addresses do not match, nodes 1 through 5 update and broadcast the received packet.
The broadcast packet from the nodes 1 through 5 arrives at one-hop nodes located from the nodes 1 through 5. Specifically, the packet from the node 1 reaches the node 6 and the node 7, and the packet from the node 2 reaches the destination node and the node 8. The packet from the node 3 reaches the node 9 and the node 10, and the packet from the node 4 reaches the node 11 and the node 12. The packet from the node 5 reaches the node 13 and the node 14. The nodes 6 through 14 and the destination node receive the packet from the single node as shown in FIG. 1. However, the nodes 6 through 14 and the destination node can receive any packet from their one-hop nodes. That is, the nodes 6 through 14 and the destination node can receive at least two packets.
The nodes 6 through 14 compare the destination address contained in the received packet with their addresses. As the destination address and their addresses do not match, the nodes 6 through 14 broadcast the received packet. The destination node recognizes that the destination address of the received packet and its address match. Therefore, the routing path can be set from the source node to the destination node. As shown in FIG. 1, all the nodes in the ad-hoc network participate in the blind flooding method. As a result, other nodes excluding the nodes substantially required for the route setup are induced to participate in the blind flooding, and the participating nodes consume power.
FIG. 2 depicts another example of the packet flooding from a source node to a destination node (not shown). Table 1 shows the relationship of nodes in the ad-hoc network. Especially, Table 1 shows the number of nodes connected to the respective nodes.
TABLE 1Number of connectedNodenodesSource5nodeNode 13Node 26Node 32Node 44Node 52Node 61Node 72Node 81Node 91Node 101Node 111Node 121. . .. . .
The nodes in the ad-hoc network know their one-hop nodes and information of Table 1. The following explains how the source node floods the packet to the destination node (not shown).
The source node acquires its one-hop nodes and the number of nodes connected to each one-hop node. The one-hop nodes from the source node are nodes 1 through 5. The source node chooses a node having the maximum number of connected nodes among the one-hop nodes based on Table 1. That is, the source node selects the node 2. The source node unicasts a packet to the selected node 2. The node 2 repeats the same operation as the source node, and thus sets a route from the source node to the destination node.
The packet is transferred to the node having the maximum number of the connected nodes among the one-hop nodes because of the higher probability that the packet is delivered to the destination node, as compared with the node having a relatively smaller number of the connected nodes. Note that the nodes in the ad-hoc network should store the information of Table 1 according to the packet flooding method as shown in FIG. 2. In addition, the nodes in the ad-hoc network, which are movable, have to update the information of Table 1 at predetermined time intervals. To update the information of Table 1, the nodes in the ad-hoc network need to check the one-hop nodes at predetermined time intervals, which causes power consumption.
Alternatively, the nodes in the ad-hoc network can recognize only the relationship between nodes located within a certain hop. This method is advantageous in that the nodes only need to recognize the information in part among the information organized in Table 1. However, it is required to update the node relationships at predetermined time intervals.